package 我的Java学习_算法基础.day_03;

import java.util.Random;

import static 我的Java学习_算法基础.day_01.唯一成对的数.printArray;

public class _035_快排之三指针分区法 {
    public static void main(String[] args) {
        int[] array = new int[10];
        Random random = new Random();
        for (int i = 0 ;i<array.length;i++){
            array[i]= random.nextInt(20);
        }
        printArray(array);
        quickSort3(array,0,array.length-1);
        printArray(array);
    }
    public static void quickSort3(int[] array,int p,int r){
        if(p<r){
            int[] a =partition3(array,p,r);
            int left = a[0],right = a[1];   //区间内与主元相同，不参与排序
            quickSort3(array,p,left-1);
            quickSort3(array,right+1,r);
        }

    }
    public static int[] partition3(int[] array,int p,int r){
        int pivot = array[p];
        int e=p+1,left=p+1,right=r;
        while(left<=right){
            while(left<=right&&array[left]<pivot){//加上：left<=right防止数组下标越界
                int x = array[left];
                array[left] = array[e];
                array[e] = x;
                left++;
                e++;
            }
            while(left<=right&&array[left]==pivot){
                left++;
            }
            while(left<=right&&array[left]>pivot){
                int y = array[left];
                array[left] = array[right];
                array[right] = y;
                right--;
            }
        }
        e--;    //最后一个小于主元的元素，与主元交换
        int x = array[e];
        array[e] = array[p];
        array[p] = x;
        int[] target = new int[2];
        target[0] = e;
        target[1] = right;
        return target;
    }
}
